/**
 * @author xinjie.txt
 * @time: 2020年7月2日 下午5:34:34
 */
package com.jiepu.daily.corejava.day0702.sort;

import java.util.Arrays;

/**
 * @Description: c）插入排序: 排序过程的某一中间时刻，R被划分成两个子区间R[1．．i-1]（已排好序的有序区）和
 *               R[i．．n]（当前未排序的部分，可称无序区）。
 *               插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1．．i-1]中适当的
 *               位置上，使R[1．．i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。
 *               插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的
 *               牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确
 *               的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。 Insertion.java
 * @author xinjie.txt
 */
public class Insertion {

	/**
	 * @Description:
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] array = { 63, 45, 18, 89, 57, 93, 20, 35, 41, 76 };
		System.out.println("初始值：  ");
		PrintArray(array);

		System.out.println();
		insertSort(array);

		System.out.println("排序后： \n");
		PrintArray(array);

	}

	/**
	 * 
	 * @Description: 打印数组
	 * @param array
	 */
	public static void PrintArray(int[] array) {
		System.out.println(Arrays.toString(array));

	}// PrintArray

	public static void insertSort(int array[]) {
		// 便利无序数组 ， 判断待排元素 array[i]
		for (int i = 1; i < array.length; i++) {
			int temp;
			// 待排元素 array[i] 小于有序序列的最后一个元素时，向前插入
			if (array[i] < array[i - 1]) {
				temp = array[i];
				//  逆向遍历有序数组   具体插入到第几位
				for (int j = i; j >= 0; j--) {
					//
					if (j > 0 && array[j - 1] > temp) {
						// 元素后移一位
						array[j] = array[j - 1];
					} else {
						// array[i] 的插入位置
						array[j] = temp;
						break;
					}
				}
			} // fi
		}
	}// insertSort

}
